% !Mode:: "TeX:UTF-8"
\chapter{相关理论和技术}

\section{引言}

影响最大化问题是在社交网络中寻找一个种子节点集合，使得在特定的传播模型下，信息从该集合出发可以传播地最广。本章对基于情绪传播的社交影响最大化研究中涉及到的相关理论和技术进行简要的介绍和分析。

\section{文本情感分析}

\subsection{情感分析定义}

情感分析（也称为意见挖掘）是通过文本分析、计算语言学和自然语言处理等方法分析作者发布的文本中含有的主观态度，这个态度或许是作者对某件事的主观判断，或者是作者当时的情感状态，又或者是作者向其读者和朋友表达的情感交流。

一般来说，情感分析包括两个重要的方面：情感极性和情感强度。情感极性是指文本对应的情感类别，通常分为正面情绪和负面情绪，有些研究中也会加入中性情绪。结合社会学和传播学，更贴近实际应用的情感分析还会加入”高兴”，”愤怒”，”悲伤”等更复杂的情绪状态。情感强度是对每种情感极性的强弱的定量表示。在很多应用中，只需要对文本进行情感极性的分类， 即找出情感强度最大的那个情感极性。

因此情感分析可以按如下定义：给定一个文本$D$（或者是文章句子等）和情感极性集合，将文本$D$映射到情感极性集合的一个类别中。情感分析方法旨在找到这个文本到情感类别的映射函数。

\subsection{情感分析方法}

\subsubsection{基于词典的方法}
最初做情感分析是通过建立情感词典的方法。Tong\cite{tong2001operational}针对电影的评论建立了一个情感词典。他首先从影评中抽取与情感相关的词汇，并将这些词汇人工分类为积极（positive）情绪或消极（negative）情绪，最后将这些词汇汇集到一个情感词典中。有了情感词典以后，对于新的影评，就可以根据影评匹配的情感词对影评进行情绪分类。这种做法由于是人工对情感词进行分类，做一个情感词典十分耗时，而且针对不同的领域和不同的应用场景可能需要重新建立不同的情感词。为了克服这种弊端，Hu和Liu\cite{hu2004mining}在使用情感词典的时候，不是要求文本中的词完全命中词典中的情感词，而是利用WordNet中的同义词和近义词关系，来判断文本中词的语义倾向，从而判断文本的情感极性。该方法对于不同的应用一般不需要重新建立情感词典，通过同义词和近义词的方法可以大幅度扩大情感词典的使用范围，避免了新增词典带来的巨大工作量。

尽管Hu和Liu对词典的方法进行了拓展，该方法仍存在许多问题。首先，基于词典的方法只考虑了情感词，而没有包含一些隐含情绪的词汇，比如”地震”，”海啸”等关于自然灾害的词汇往往包含很多负面情绪，而”校庆”，”国庆”这种词又往往包含许多正面情绪，这些词是没有办法通过情感词典分类到正确的情绪中的。其次，基于词典的方法只分析情感词汇是否命中情感词典，而忽略了句子中否定词对情感的影响，造成文本情感分类准确率不高。

为了克服靠人工建立的词典在情感解释力上的不足，Liu\cite{liu2003model}等使用Open Mind Common Sense对人类通用情感进行学习和解释。Open Mind Common Sense是一个常识知识库，可以用来对客观世界中的事件、行为和对象进行通用的情感推理。该方法首先从知识库中选出典型的六类情感词汇（高兴、悲伤、愤怒、恐惧、厌恶和惊奇），然后根据知识库中的概念关系对其他概念进行情感赋值。比如，知识库中有两句话：“发霉的面包很恶心”，“新鲜的面包很美味”。那么，在“恶心”和“美味”分别被归类为厌恶和高兴的基础上，修饰语言模型（Modifier Unigram Model）可以分别将发霉和新鲜这两个修饰语也判断为表示厌恶和高兴的概念。

在中文文本识别方面，用情感词汇来判断文本情感的方法相对较少。金聪等\cite{jincong2008}将Turney的PMI-SO方法应用到对中文语料的情感判断上，同时用典型文档的语义倾向值的平均值作为阈值来代替零值作为两级情感的分类界限，改善了分类效果。李钝\cite{lidun2008}从语言学角度出发，分析词典中的词对语义的特点，采用“情感倾向定义”权重优先的方法计算短语中各词的语义倾向度，然后分析短语中各词组合方式的特点，提出中心词概念来对各词的倾向性进行计算，以识别短语的倾向性和倾向强度。实验表明，该方法对短语的倾向分类识别效果较好，可为更大粒度的文本倾向识别打好基础。

\subsubsection{机器学习的方法}

随着机器学习的兴起，近几年来基于机器学习情感分类方法不断涌出。基于机器学习的方法通过建立一个分类模型，并根据已经标注好的文本及其情绪数据对模型参数进行估计，得到分类器。利用训练好的分类器就可以对未知文本进行情绪分类。

Pang和Li等\cite{pang2002thumbs}采用不同的特征选择方法，应用朴素贝叶斯、最大熵和支持向量机模型对电影评论进行分类。他们在另一项工作中\cite{pang2004sentimental}，将文本极性分类问题转换成求句子连接图的最小分割问题，实现了一个基于minimum-cut 的分类器。Pang等的研究表明，基于机器学习的分类器要比手工分类效果好很多，而在三类分类器中，支持向量机分类器的表现比朴素贝叶斯和最大熵好。实验结果同时还表明对文本的情感分类效果远差于对文本主题的分类。Ni等\cite{ni2007exploring}利用卡方检验和信息增益进行特征选择，并采用朴素贝叶斯、支持向量机和Rocchio’s算法进行情感分类。Mullen\cite{mullen2004sentiment}和Whitelaw等\cite{whitelaw2005using}同样使用支持向量机模型，不过他们在特征选择和处理上的方法不同。Cui等\cite{cui2006comparative}使用了PA（Passive Aggressive）、LM（Language Modeling）和Winnow分类器，并比较了它们的性能。他们的对比实验结果表明，平均表现最好的是PA分类器，Winnow次之，LM最差。

对于需要多个情感极性的应用，例如需要将文本分为高兴、愤怒、厌恶等情绪，\cite{zhao_moodlens:_2012}提出了一个很好的解决方法。作者通过文本中的表情符自然地对文本进行情绪标注，最后利用朴素贝叶斯方法对标注数据进行建模，得到四分类器。该方法简单直观并且取得了不错的分类准确率。

\subsubsection{深度学习的方法}

深度学习这几年在计算机视觉、语音识别和自然语言处理等领域取得了出色的效果。Kim在\cite{kim2014convolutional}中提出了使用卷积神经网络对句子进行情感分类的方法。他们首先将文本中的每个词映射到不同的词向量，然后在词向量上层加入卷积层，最大池化层并送入Softmax分类器，该模型的结构见图\ref{fig:cnn}。文中对比了不同的词向量获取方法，包括使用Word2vec模型\cite{mikolov2013distributed}预训练的词向量和随机初始化的词向量。Severyn等\cite{severyn2015unitn}使用了与\cite{kim2014convolutional}中类似的结构，并在Semeval-2015比赛的message-level情感分类任务中，获得了第二名的成绩。

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.8\textwidth]{figure/chap2/cnn.png}
\caption{文本情感分类的卷积神经网络结构}
\label{fig:cnn}
\end{figure}

\section{信息传播模型}

一个社交网络可以被定义为一个有向图$G=(V, E)$，其中集合$V$中的每一个节点表示一个用户，集合$E$中的每一条边表示用户之间的关注关系。

假设社交网络中的信息传播发生在每个离散时间。那么在时刻$t$，如果一个节点接受了信息，它将从非激活状态转移到激活状态，否则它仍然保持非激活状态。一个节点接受信息的可能性与它处于激活状态的邻居个数成正比。一个完整的信息传播过程如下：信息从一个初始化为激活状态的节点集合开始，通过随机传播过程激活其他节点，这些新激活的节点以同样的方式激活更多的节点，直到没有新的节点被激活时，信息传播过程停止。

信息传播模型是对信息随机传播过程的建模。在本节中，我们介绍两种典型的信息传播模型：独立传播模型和线性阈值模型。

\subsection{独立传播模型}
\label{sec2.3.1}

在独立传播模型中，每一条边都有一个传播概率，即对于每一条边$(v,u)\in E$，$p_{v, u}$表示信息从节点$v$传播到节点$u$的概率。这个概率可以通过用户交互频率、地理位置或者历史信息传播轨迹等方式来确定。在$t$时刻，一个节点一旦被激活，它在$t+1$时刻就有唯一一次机会激活它的邻居，激活概率即为边的传播概率。根据\cite{Shakarian2015}的描述，在基于独立传播模型的信息传播过程中，假设$D(t-1)$表示在$t-1$时刻新激活的节点，那么在$t$时刻，$v \in D(t-1)$有一次机会以$P_{v,u}$的概率影响它处于非激活状态的邻居$u \in N_{out}(v)$，其中$N_{out}(v)$表示$v$指向的邻居。

图\ref{fig-ic-example}是独立传播模型的一个例子，它完整的模拟了一次信息从初始节点集合出发的传播过程，其中不同子图分别表示不同时刻的网络状态。如\ref{fig-ic-example-a}所示，激活的节点用黄色来表示，初始时节点$C$和节点$D$处于激活状态。在下个时间点，$C$有机会激活它的邻居$A$，$G$和$H$而$D$有机会激活它的邻居$B$，$E$和$F$。根据\ref{fig-ic-example-b}，只有三个节点$A$，$H$和$E$被成功激活了，而初始为激活的节点变为灰色（表示它们已经没有机会再去激活其它节点）。同样在\ref{fig-ic-example-c}中，$F$和$G$被成功激活。最后，$F$有0.5的概率激活$I$，但是如\ref{fig-ic-example-d}所示，$F$没有成功激活$I$。此时由于没有更多被激活的节点，信息传播过程停止。最终，在独立传播模型下，信息从节点C和D出发，一共影响了七个节点。

\begin{figure}[h!]{}
    \centering
    \begin{tabular}{cc}
        \subfigure[]{
            \label{fig-ic-example-a}
            \includegraphics[width=.40\textwidth]{figure/chap2/ic_a.png}
        } \hspace{3em} &
        \subfigure[]{
            \label{fig-ic-example-b}
            \includegraphics[width=.40\textwidth]{figure/chap2/ic_b.png}
        } \\
        \subfigure[]{
            \label{fig-ic-example-c}
            \includegraphics[width=.40\textwidth]{figure/chap2/ic_c.png}
        } \hspace{3em} &
        \subfigure[]{
            \label{fig-ic-example-d}
            \includegraphics[width=.40\textwidth]{figure/chap2/ic_d.png}
        }\\
    \end{tabular}
    \caption{独立传播模型的信息传播过程}
    \label{fig-ic-example}
\end{figure}

\subsection{线性阈值模型}

在线性阈值模型中，每一条边都有一个权重，即对于每一条边$(v,u)\in E$，$b(v,u)$表示节点$v$影响$u$的非负权重。对于任何$v \in V$，所有指向它的边的权重之和小于等于1。同样根据\cite{Shakarian2015}中的描述，在基于线性阈值模型的信息传播过程中，每个节点$v$从区间$[0, 1]$中随机选择一个阈值$\theta_{v}$。假设$H(t-1)$表示在$t-1$时刻时处于激活状态的节点，则在$t$时刻，如果处于非激活状态的节点$v$若满足$\sum_{u \in N_{in}(v) \cap H_{t-1}}{b(u, v)} \geqslant \theta_{v}$，那么它将被激活。其中，$N_{in}(v)$表示指向$v$的邻居，$N_{in}(v) \cap H_{t-1}$表示$v$处于激活状态的邻居。

可以看出，在每个时刻一个处于非激活状态的节点会被其所有处于激活状态的邻居共同影响。每个邻居对它的影响由边的权重决定，当权重之和超过节点阈值时，节点就被激活。

图\ref{fig-lt-example}是线性阈值模型的一个例子，它完整的模拟了一次信息从初始节点集合出发的传播过程，其中不同子图表示不同时刻的网络状态。如图\ref{fig-lt-example-a}所示，每个节点都被随机赋予了一个阈值且节点$C$和$D$初始化为激活状态。节点$C$不能激活节点$G$和$H$因为边的权重没有达到阈值，但是它可以激活节点$A$（$0.2 \geqslant 0.1$）。同样，节点$D$可以激活节点$F$（$0.4 \geqslant 0.3$）而不能激活节点$B$和$E$。在下一个时刻（图\ref{fig-lt-example-b}），有四个处于激活状态的节点并且它们可以激活节点$I$（$0.3 + 0.5 \geqslant 0.2$）和节点$E$（$0.4 + 0.2 \geqslant 0.5$）。在之后的时刻，没有更多的节点可以被激活，信息传播过程停止。最终，在线性阈值模型下，信息从节点C和D出发，一共影响了6个节点。

\begin{figure}[h!]{}
    \centering
    \subfigure[]{
        \label{fig-lt-example-a}
        \includegraphics[width=.4\textwidth]{figure/chap2/lt_a.png}
    }
    \hspace{3em} % 水平间隔
    \subfigure[]{
        \label{fig-lt-example-b}
        \includegraphics[width=.4\textwidth]{figure/chap2/lt_b.png}
    }
    \hspace{3em} % 水平间隔
    \subfigure[]{
        \label{fig-lt-example-c}
        \includegraphics[width=.4\textwidth]{figure/chap2/lt_c.png}
    }
    \caption{线性阈值模型的信息传播过程}
    \label{fig-lt-example}
\end{figure}

\section{影响最大化}

\subsection{影响最大化定义}

给定社交网络$G=(V,E)$，集合$S$表示在信息传播开始时处于激活状态的节点集合，即种子节点集合，$RanCas(S)$表示信息从集合$S$出发，在给定信息传播模型下，最终能影响的节点集合，即最终处于激活状态的节点集合。因此，定义集合$S$的影响范围为|RanCas(S)|。

将集合$S$的大小$k$以及社交网络$G$作为输入，在给定的信息传播模型下，找到$k$个种子节点，使得这$k$个种子节点能影响范围最大，也即使得这$k$个种子节点的影响最大化。

\subsection{影响最大化算法}

影响最大化算法通常有两种类型。其中一类方法只跟网络结构有关，例如基于节点度数的方法。该方法按节点的度数从高到低排序选择$k$个节点作为种子节点集合。但是由于度数高的节点很可能聚合在同一个社团内，他们的影响范围也只局限在一个很小的范围内，因此该方法的效果较差。

另一类算法是通过在特定信息传播模型下模拟信息传播过程，来寻找种子节点集合。对于独立传播模型和线性阈值模型，影响最大化问题是NP-hard的，无法获得其精确解，因此学者们提出了许多近似算法。

下面介绍一些典型的影响最大化算法，包括它们的原理和算法流程。

\subsubsection{贪心算法}

贪心算法的基本思想是每次选择一个节点加入到种子节点集合中，并保证加入该节点后可以新增加的影响范围最大。

Kempe首先根据上述思想提出影响最大化的贪心算法，算法\ref{alg:greedy}描述了该算法的流程：首先将种子节点集合初始为空，之后每一轮算法扫描所有不在种子节点集合中的节点，并选择一个节点加入到种子节点集合中，使得加入该节点后种子集合的影响最大（算法第10行）。这也意味着新加入的节点在当前轮可以使影响增加地最多。这样重复$k$次后，就得到了一个大小为$k$的种子节点集合。为了计算加入新节点后种子节点集合的传播范围，算法需要对$S \cup \{v\}$进行$R$次模拟传播过程$RanCas(S \cup \{v\})$来得到一个相对稳定的平均值，通常$R$取20000。每次计算$RanCas(S)$的时间复杂度为$O(|E|)$，因此贪心算法的总时间复杂度为$O(kR|V||E|)$。

在说明贪心算法的精度保证之前，先介绍函数的单调性与子模块性概念。

子模块性：对于一个将有穷集合映射到非负实数的函数$f$，如果将一个元素$v$加入到集合$S$后所获得的边际收益不小于将其加入到$S$的超集中获得的边际收益，那么称该函数$f$具有子模块性。满足子模块性的函数$f$可以形式化表示为：
$$f(S \cup \{v\}) - f(S) \ge f(T \cup \{v\}) - f(T)$$
对于任意的$v$和$S \subseteq T$均成立。

单调性：对于一个将有穷集合映射到非负实数的函数$f$，如果将一个元素$v$加入到集合$S$后函数值不小于$S$本身的函数值，那么称函数$f$具有单调性。满足调性的函数$f$可以形式化表示为：
$$f(S \cup \{v\}) \ge f(S)$$
对于任意的$v$和$S$均成立。

Nemhauser G L等人\cite{nemhauser1978analysis}证明，一个函数$f$如果同时满足单调性和子模块性，则通过上述贪心方式得到的集合$S$效果能达到最优集合$S^*$效果的$1-\frac{1}{e}$。也就是说，
$$f(S) \ge (1-\frac{1}{e})f(S^*)$$

Kempe之后证明，在独立传播模型和线性阈值传播模型下，信息传播过程$|RanCas|$满足单调性和子模块性。因此，上述贪心算法可以达到最优效果的$1-\frac{1}{e}$。

\begin{algorithm}[h!]
\caption{Greedy($G$, $k$)}
\label{alg:greedy}
\begin{algorithmic}[1]
\STATE 初始化 $S = \emptyset$ and $R = 20000$
\FOR {$i = 1$ to $k$}
\FOR {each vertex $v \in V \backslash S$}
\STATE $s_v = 0$
\FOR {$i = 1$ to $R$}
\STATE $s_v += |RanCas(S \cup \{v\})|$
\ENDFOR
\STATE $s_v = s_v / R$
\ENDFOR
\STATE $S = S \cup \{{argmax_{v \in V \backslash S}{\{S_v\}}}\}$
\ENDFOR
\STATE 输出$S$     
\end{algorithmic}
\end{algorithm}

\subsubsection{CELF算法}

在上述的贪心算法中，每一轮我们都需要遍历不在种子节点集合中的所有其他节点，这使得贪心算法的效率很低。Leskovec等在\cite{leskovec_cost-effective_2007}中提出了Cost-Effective Lazy Forward（CELF）算法，该算法利用$|RanCas(S)|$的子模块性，大大减小了每一轮所需要遍历的种子节点个数。

具体来说，由于$|RanCas(S)|$具有子模块性，将节点$v$加入到种子节点集合$S$中时，集合$S$越小，加入$v$后能获得的边际收益越大。因此，如果当前轮加入$v$能获得的边际收益大于前一轮加入$u$能获得的边际收益，当前轮就不再需要遍历$u$。举例来说，假如现在有节点集合$V=\{v_1, v_2, v_3, v_4, v_5\}$，初始时种子节点集合$S$为空。在第一轮遍历完$V$中的所有节点之后，得到每个节点的边际收益如下表\ref{tab-mg-iter1}：

\begin{table}
    \centering
    \caption{CELF算法第一轮中节点边际收益结果}
    \label{tab-mg-iter1}
    \begin{tabular}{lcr}
    \toprule
    节点 & 边际收益 & 当前轮数 \\
    \midrule 
    $v_1$ & 15 & 1 \\
    $v_2$ & 11 & 1 \\
    $v_3$ & 9 & 1 \\
    $v_4$ & 5 & 1 \\
    $v_5$ & 3 & 1 \\
    \bottomrule
    \end{tabular}
\end{table}

由于节点$v_1$的边际收益最高，因此我们将其加入到种子节点集合$S$中。在寻找第二个种子节点时，我们按上一轮的边际收益从大到小的顺序开始遍历，即从节点$v_2$（$v_1$已经被加入种子节点集合）开始遍历。假设遍历完$v_2$和$v_3$后，得到每个节点的边际收益如下表\ref{tab-mg-iter2}：

\begin{table}
    \centering
    \caption{CELF算法第二轮中节点边际收益结果}
    \label{tab-mg-iter2}
    \begin{tabular}{lcr}
    \toprule
    节点 & 边际收益 & 当前轮数 \\
    \midrule 
    $v_2$ & 8 & 2 \\
    $v_3$ & 6 & 2 \\
    $v_4$ & ? & 2 \\
    $v_5$ & ? & 2 \\
    \bottomrule
    \end{tabular}
\end{table}

根据子模块性，在第二轮中节点加入$S$后获得的边际收益一定小于第一轮。而在遍历完$v_3$后我们发现，$v_3$第二轮获得的边际收益大于$v_4$和$v_5$第一轮获得的边际收益。因此，我们可以选择当前轮边际收益最大的$v_2$加入到种子节点集合$S$中，而不需要再去考虑$v_4$和$v_5$的结果。

通过上述例子，可以直观地发现在CELF算法中，每一轮所需要遍历的节点个数远小于原始贪心算法。因此该算法的效率比原始贪心算法高得多，如\cite{leskovec_cost-effective_2007}中的实验结果，在一些社交网络中，CELF算法速度可以达到原始贪心算法的700倍。

\subsubsection{NewGreedy算法}

虽然CELF算法可以将贪心算法在时间上优化700倍，但是其仍然无法满足大规模社交网络的要求。陈为在\cite{chen_efficient_2009}中提出了一种新的贪心算法，称为NewGreedy算法，该算法在每一轮中只需要一次遍历网络，就可以找出边际收益最大的种子节点。

我们知道在独立传播模型中，$RanCas(S)$的工作方式如下。假设$A_i$表示在第$i$轮被激活的节点集合，且$A_0 = S$。对于任意的$(v,u) \in E$，如果$v \in A_i$且$u$当前处于非激活状态，那么$v$都有一定的概率$p$激活$u$。换句话说，如果$A_i$中有$l$个$u$的邻居，那么$u \in A_{i+1}$的概率为$1-(1-p)^l$。直到$A_{i+1} = \emptyset$时，$RanCas(S)$过程停止。

我们注意到，在信息随机传播过程$RanCas(S)$中，每条边$(v, u) \in E$只有一次机会决定信息是否从$v$传播到$u$。因此，我们可以提前决定信息是否通过边$(v, u)$传播，即删除那些没有信息通过的边。这样，我们可以得到一个新的网络$G'$。通过这种转换，求$RanCas(S)$就简化为求集合$S$的可达节点。这样做的好处是当我们生成了$G'$以后，只需要一次线性扫描就可以获得$S$在$G'$中的可达节点集合$R_{G'}(S)$以及所有节点$v \in V$的可达节点集合$R_{G'}(\{v\})$。因此，对于任意的$v \in V \backslash S$，$v$加入到种子节点集合后可以新增的影响范围$s_v$就可以很容易地计算：$$s_v = \begin{cases}|RanCas(\{v\})|, & if\ v \notin R_G'{(S)} \cr 0, &otherwise\end{cases}$$

通过随机生成$R$次$G'$，每次生成$G'$后根据上述公式计算每一个$v \in V \backslash S$的新增影响范围$s_v$，我们就能得到每一轮的最优种子节点。算法\ref{alg:newgreedy}描述了这个过程，由于一次遍历$G'$（通过深度优先搜索或广度优先搜索）即可得到所有的$R_{G'}(\{v\})$和$R_{G'}(S)$，因此算法\ref{alg:newgreedy}的复杂度为$O(kR|E|)$，比传统的贪心算法快了$|V|$倍。

\begin{algorithm}[h!]
\caption{NewGreedy($G$, $k$)}
\label{alg:newgreedy}
\begin{algorithmic}[1]
\STATE 初始化 $S = \emptyset$ and $R = 20000$
\FOR {$i = 1$ to $k$}
\STATE 对于所有的$v \in V \backslash S$，令$s_v=0$
\FOR {$i = 1$ to $R$}
\STATE 以$1-p$的概率移除$G$中的每条边，得到新的网络$G'$
\STATE 计算$R_{G'}{(S)}$
\STATE 对于所有的$v \in V$，计算$|R_{G'}{(\{v\})}|$
\FOR {each $v \in V \backslash S$}
\IF {$v \notin R_{G'}{S}$}
\STATE $s_v += |R_{G'}{(\{v\})}|$
\ENDIF
\ENDFOR
\ENDFOR
\STATE 对于所有的$v \in V$，计算$s_v = s_v / R$
\STATE $S = S \cup \{{argmax_{v \in V \backslash S}{\{S_v\}}}\}$
\ENDFOR
\STATE 输出$S$     
\end{algorithmic}
\end{algorithm}

\subsubsection{Collective Influence算法}

Collective Influence算法是Morone和Makse\cite{morone_influence_2015}
在2015年提出的复杂网络中的影响最大化算法，该算法没有借助任何信息传播模型，而是基于网络的物理性质来寻找种子节点集合。其思想是移除使得网络的能量函数递减最快的节点，文中给出了寻找这些节点的算法，即Collective Influence(以下简称CI)算法。

Morone和Makse提到，在网络中寻找一个节点集合使得信息扩散最大的问题可以用渗透理论来解决，其目标是寻找对网络的连通性影响最大的节点集合。考虑一个包含$n$个节点和$m$条边的网络，令向量$\vec n = (n_1, n_2, \dots , n_3)$表示节点是否被删除（$n_i=0$）或保留（$n_i=1$）。令$i \to j$表示由节点$v_i$指向节点$v_j$的边，那么寻找种子节点集合的问题就转换寻找一个向量$\vec n$，使得矩阵$M$的最大特征值最小，其中矩阵$M$为：
$$M_{k \to l, i \to j}  \equiv \frac{\partial v_{i \to j}}{\partial v_{k \to l}}|\{v_{i \to j}=0\}$$

Morone和Makse给出了求解$\vec n$的方法，即CI算法。首先定义每个节点$v$周围半径为$l$的球$Ball(v, l)$为从$v$出发，且距离$v$最短路径小于等于$l$的节点集合。球的表面$\partial Ball(v, l)$为从$v$出发，且距离$v$最短路径恰好等于$l$的节点集合。令$k_v$表示节点$v$的度数，则一个节点$v$的CI值为：$$CI_{l}{(v)} = (k_v - 1) \sum_{u \in \partial Ball(v, l)}{(k_u - 1)}$$

有了上述定义，CI算法的流程如算法\ref{alg:ci}所示。即在每一轮中，算法计算每个节点的CI值，并选择一个CI值最大的节点加入到种子集合$S$中，直到集合$S$的大小达到$k$。在实际应用中，我们可以自由选择$l$，$l$的值越大，算法的结果越准确。通常来说，$l$的值选3就能够达到较好的效果。

对于大型的网络，文中给出了一个优化方法，可以使该算法的计算速度达到$O(|V|log(|V|))$。我们注意到在算法的第5行中，每次只选择一个CI值最大的节点加入到种子集合中。为了加快计算速度，我们也可以按CI值从大到小选择多个节点加入到集合中。文中提到若$|V|$很大，该算法在提升速度的同时仍能保持很好的效果。

\begin{algorithm}[h!]
\caption{CI($G$, $k$)}
\label{alg:ci}
\begin{algorithmic}[1]
\STATE 初始化 $S = \emptyset$
\STATE 对于所有的$v \in V$，计算$k_v$
\FOR {$i = 1$ to $k$}
\STATE 对于所有的$v \in V$，计算$CI_{l}{(v)}$
\STATE $v* = argmax_{v \in V \backslash S}{\{CI_{l}{(v)}\}}$, $S = S \cup \{v*\}$
\STATE 对于所有的$(v, u) \in E$，更新$k_u = k_u - 1$。
\ENDFOR
\STATE 输出$S$
\end{algorithmic}
\end{algorithm}

\section{本章小结}

本章简要介绍了基于情绪传播的社交影响最大化研究中涉及到的相关理论和技术：
\begin{itemize}
\item 情感分析技术，包括基于词典、机器学习和深度学习的方法。
\item 信息传播模型，包括独立传播模型和线性阈值模型。
\item 影响最大化算法，包括贪心算法，CELF算法，NewGreedy算法以及CI算法。
\end{itemize}